package com.example.demo.suanfa_heap;

import com.example.demo.Utils;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

/**
 * @program: java_base
 * @description: 加强堆-相对于java自带的优先队列堆PriorityQueue
 * @author: zhouhongtao
 * @happyCreateTime: 2022/02/17 09:42
 */
public class HeapGreaterDemo<T> {

    private ArrayList<T> heap;
    private int heapSize;
    private HashMap<T, Integer> indexMap;
    private Comparator<? super T> comp;

    public HeapGreaterDemo(Comparator<T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public T peek() {
        return heap.get(0);
    }

    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    /**
     * 大根堆
     *
     * @param index
     */
    private void heapInsert(int index) {
        while (comp.compare(heap.get((index - 1) >> 1), heap.get(index)) < 0) {
            Utils.swap02(heap, (index - 1) >> 1, index);
            index = (index - 1) / 2;
        }
    }

    public T pop(){
        if (heap.isEmpty()){
            return null;
        }
        T t = heap.get(0);
        Utils.swap02(heap,0,heapSize-1);
        indexMap.remove(t);
        heap.remove(--heapSize);
        heapify(0);
        return t;
    }

    private void heapify(int index) {
        int left = index << 1 + 1;
        while (left < heapSize){
            // 确定是否有右孩子
            int maxIndex = left + 1 > heapSize ? left + 1 : left;
            // 确定 左边孩子 和 maxIndex 孩子那个大？
            maxIndex = comp.compare(heap.get(left), heap.get(maxIndex)) < 0 ? left : maxIndex;

        }
    }

}
